COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Additions to readin:
C00003 00003	\exercise The Goodstein function
C00007 ENDMK
C⊗;
Additions to readin:

goodstein function:

let

Revise discussion of equality to base it on \equal
morris

Revise last exercise in reada to offer several forms of polynomial
representation and ask the reader to compare their relative
advantages.

Put examples of terms with variables into the table of terms and
values.
\exercise The Goodstein function

	This rather famous numerical function requires a recursion quite
different from those we have previously studied.

	We first need hereditary $n$-ary notation for
writing natural numbers (non-negative integers).  As in ordinary
$n$-ary notation we expand the numbers in powers of $n$.  However,
we write out powers explicitly.  Moreover, we also write the exponents
in hereditary $n$-ary notation.  We leave out terms with zero
coefficients, omit the coefficient when it is 1, omit the power
when the exponent is zero and omit the exponent when it is 1.  We
therefore have in hereditary binary and ternary

$$\halign{\hfill$#$&$#$\hfill\cr
1&=1\cr
2&=2\cr
3&=2+1\cr
5&=2↑2+1\cr
7&=2↑2+2+1\cr
9&=2↑{2+1}+1\cr
63&=2↑{2↑2+1}+2↑{2↑2}+2↑{2+1}+2↑2+2+1\cr
5861&=2\cdot3↑{2\cdot3+1}+2\cdot3↑{2\cdot3}+3↑3+2
}.$$
%
	The function $goodstein(n)$ begins by expressing $n$ in
hereditary binary.  Then it subtracts $1$ keeping the result in
hereditary binary.  Then all the $2$s in the number are changed
to $3$s getting a number in hereditary ternary.
 Again subtract 1 keeping the result in hereditary
ternary.  Change all the $3$s to $4$s getting a number in hereditary
quaternary.  Continue this process until $0$ is reached.
$goodstein(n)$ is the number of times $1$ is subtracted.
We have
%
$$\halign{\hfill$#$&$#$\hfill\cr
goodstein(1) &= 1\cr
goodstein(2) &= 2\cr
goodstein(3) &= 4\cr
goodstein(5) &= 24\cdot2↑{24\cdot(2↑{24}+1)} -2\cr}.$$
%
	(i) Verify the value of $goodstein(5)$.

	(ii) Write a \lisp\ function for evaluating $goodstein(n)$
even though it won't even be able to compute $goodstein(5)$.

	(iii) Can the value of $goodstein(6)$ be written on a single
page using only the arithmetic operations including exponentiation?

\noindent Mathematical remarks:

	(i) $goodstein(n)$ grows very rapidly.  Compared to its
growth, that of the Ackermann function is trivial.

	(ii) Proving that the computation of $goodstein(n)$ terminates
cannot be done in formalized arithmetic or the equivalent formalism
of chapter 3 of this book using only ordinary mathematical or
structural induction.  In the terminology of mathematical logic,
it requires induction up to $\epsilon↓0$.

	(iii) In fact the termination of $goodstein(n)$ for all $n$,
together with formalized arithmetic, can be used to prove the consistency
of arithmetic with the ordinary mathematical induction rule.

	We shall do more with $goodstein(n)$ in \chapref{provin}.